package com.xxd.algo.newcode.base01.class07;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-01-11 14:10
 * @description:
 */
public class IPO {

    public static class Node {
        public int p;
        public int c;

        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }


    public static class MinCostComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c;
        }
    }

    public static class MaxProfitComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o2.p - o1.p;
        }
    }

    /**
     * @param k       最多做多少个项目
     * @param m       初始资金
     * @param profits 表示i号项目在扣除花费之后还能挣到的钱(利润)
     * @param capital 表示i号项目的花费
     * @return
     */
    public static int findMaximizedCapital(int k, int m, int[] profits, int[] capital) {
        PriorityQueue<Node> minCost = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> maxProfit = new PriorityQueue<>(new MaxProfitComparator());

        for (int i = 0; i < profits.length; i++) {
            minCost.add(new Node(profits[i], capital[i]));
        }

        for (int i = 0; i < k; i++) {
            while (!minCost.isEmpty() && minCost.peek().c <= m) {
                maxProfit.add(minCost.poll());
            }

            if (maxProfit.isEmpty()) {
                return m;
            }

            m += maxProfit.poll().p;
        }


        return m;
    }
}
